// 一所学校里有一些班级，每个班级里有一些学生，现在每个班都会进行一场期末考试。
// 给你一个二维数组 classes ，其中 classes[i] = [passi, totali] ，
// 表示你提前知道了第 i 个班级总共有 totali 个学生，其中只有 passi 个学生可以通过考试。

// 给你一个整数 extraStudents ，表示额外有 extraStudents 个聪明的学生，
// 他们 一定 能通过任何班级的期末考。你需要给这 extraStudents 个学生每人都安排一个班级，
// 使得 所有 班级的 平均 通过率 最大 。
// 一个班级的 通过率 等于这个班级通过考试的学生人数除以这个班级的总人数。
// 平均通过率 是所有班级的通过率之和除以班级数目。
// 请你返回在安排这 extraStudents 个学生去对应班级后的 最大 平均通过率。
// 与标准答案误差范围在 10-5 以内的结果都会视为正确结果。

// 示例 1：
// 输入：classes = [[1,2],[3,5],[2,2]], extraStudents = 2
// 输出：0.78333
// 解释：你可以将额外的两个学生都安排到第一个班级，平均通过率为 (3/4 + 3/5 + 2/2) / 3 = 0.78333 。

// 示例 2：
// 输入：classes = [[2,4],[3,9],[4,5],[2,10]], extraStudents = 4
// 输出：0.53485

// 提示：
//     1 <= classes.length <= 105
//     classes[i].length == 2
//     1 <= passi <= totali <= 105
//     1 <= extraStudents <= 105

/**
 * @param {number[][]} classes
 * @param {number} extraStudents
 * @return {number}
 */
var maxAverageRatio = function(classes, extraStudents) {
    /////思路比较简单：先对其进行排序，按增长率由大到小，每一次分配学生都给每次增长率最高的班级
    ///最佳方法：大顶堆
    //////对堆排序不大熟悉，过后用堆方法做

    //////只是不知道下面的写法为何结果不对
    let len = classes.length;
    classes.sort((a, b)=>{
        let rb = ((b[0] + 1) / (b[1] + 1)) - (b[0] / b[1]);
        let ra = ((a[0] + 1) / (a[1] + 1)) - (a[0] / a[1]);
        if (ra > rb) {
            return -1;
        } else {
            return 1;
        }
    });
    console.log(classes);
    while(extraStudents > 0) {
        let c = classes.shift();
        c[0]++;
        c[1]++;
        classes.push(c);
        extraStudents--;
        
        let r1 = ((classes[0][0] + 1) / (classes[0][1] + 1)) - (classes[0][0] / classes[0][1]);
        let len = classes.length;
        let r2 = ((classes[len - 1][0] + 1) / (classes[len - 1][1] + 1)) - (classes[len -1][0] / classes[len - 1][1]);
        if (r1 < r2) {
            [classes[0], classes[len - 1]] = [classes[len - 1], classes[0]];
        }
        console.log(classes);
    }
    
    let result = 0;
    while(classes.length > 0) {
        let c = classes.shift();
        result += (c[0] / c[1]);
    }
    return result / len;
};

console.log(maxAverageRatio([[2,4],[3,9],[4,5],[2,10]], 4));

